/* -*- mode: C; c-basic-offset: 8 -*-
 *
 * malloc.c - From K&R book: The C Programming Language
 *
 */

#define NULL 0
#define NALLOC 1024	/* minimum #units to request */

typedef long Align;

union header {	/* block header */
	struct {
		union header *ptr;	/* next block if on free list */
		unsigned size;	/* size of this block */
	} s;
	Align x;	/* force alignment of blocks */
};

typedef union header Header;

static Header base;
static Header *freep = NULL;

static Header *morecore(unsigned);
void free(void *);

void *
malloc(unsigned nbytes)
{
	Header *p, *prevp;
	unsigned nunits;

	nunits = (nbytes + sizeof(Header) - 1) / sizeof(Header) + 1;
	if ((prevp = freep) == NULL) {	/* no free list yet */
		base.s.ptr = freep = prevp = &base;
		base.s.size = 0;
	}
	for (p = prevp->s.ptr; ; prevp = p, p = p->s.ptr) {
		if (p->s.size >= nunits) {	/* big enough */
			if (p->s.size == nunits)	/* exactly */
				prevp->s.ptr = p->s.ptr;
			else {				/* allocate tail end */
				p->s.size -= nunits;
				p += p->s.size;
				p->s.size = nunits;
			}
			freep = prevp;
			return (void *)(p+1);
		}
		if (p == freep)		/* wrapped around free list */
			if ((p = morecore(nunits)) == NULL)
				return NULL;	/* none left */
	}
}

/* morecore: ask system for more memory */
Header *
morecore(unsigned nu)
{
	char *cp, *sbrk(int);
	Header *up;
	
	if (nu < NALLOC)
		nu = NALLOC;
	cp = sbrk(nu * sizeof(Header));
	if (cp == (char *) -1)	/* no space at all */
		return NULL;
	up = (Header *) cp;
	up->s.size = nu;
	free((void *)(up+1));
	return freep;
}

/* calloc: returns an initialized to zero storage */
void *
calloc(unsigned n, unsigned size)
{
	void *p;

	p = malloc(n * size);
	if (p == NULL)
		return NULL;

	return memset(p, 0, n * size);
}

/* realloc: changes the size of the object pointed to by p to size */
void *
realloc(void *p, unsigned size)
{
	void *new;

	new = malloc(size);
	if (new == NULL)
		return NULL;
	
	memcpy(new, p, size); /* this is stupid */
	
	return new;
}

/* free: put block ap in free list */
void
free(void *ap)
{
	Header *bp, *p;
	
	bp = (Header *)ap - 1;	/* point to block header */
	for (p = freep; !(bp > p && bp < p->s.ptr); p = p->s.ptr)
		if (p >= p->s.ptr && (bp > p || bp < p->s.ptr))
			break; /* freed block at start or end of arena */
	
	if (bp + bp->s.size == p->s.ptr) {	/* join to upper nbr */
		bp->s.size += p->s.ptr->s.size;
		bp->s.ptr = p->s.ptr->s.ptr;
	} else
		bp->s.ptr = p->s.ptr;
	if (p + p->s.size == bp) {		/* join to lower nbr */
		p->s.size += bp->s.size;
		p->s.ptr = bp->s.ptr;
	} else
		p->s.ptr = bp;
	freep = p;
}
